package C.栈;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class _469_下一个更大的元素 {

    /**
     * 题解：用一个栈 遍历num2 进去一个元素 用下一个元素与他对比 如果大 就pop出
     * 如果小 就push进来 直到更大的元素 这样栈里所有元素都是小的 就全pop出来
     * 最后如果栈不为空 全都是-1返回值
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {

        Stack<Integer> stack = new Stack<>();
        Map<Integer,Integer> map = new HashMap<>();
        for (int num:nums2){
            if (stack.isEmpty()){
                stack.push(num);
                continue;
            }
            while ( !stack.isEmpty() && num > stack.peek()){

                    map.put(stack.pop(),num);


            }
            stack.push(num);
        }

        //优化：：可以不用pop出来 不在map里的一定就是咩有结果的 就-1

        while (!stack.isEmpty()){
            map.put(stack.pop(),-1);
        }


        for (int i=0;i<nums1.length;i++){
            nums1[i] = map.get(nums1[i]);
        }

        return nums1;
    }
}
